DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2022.23

Fault Tolerant Coloring of the Asynchronous Cycle

Authors: Pierre Fraigniaud, Patrick Lambein-Monette, and Mikaël Rabie

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

We present a wait-free algorithm for proper coloring the n nodes of the asynchronous cycle C_n, where each crash-prone node starts with its (unique) identifier as input. The algorithm is independent of n ≥ 3, and runs in O(log^*n) rounds in C_n. This round-complexity is optimal thanks to a known matching lower bound, which applies even to synchronous (failure-free) executions. The range of colors used by our algorithm, namely {0,…,4}, is optimal too, thanks to a known lower bound on the minimum number of names for which renaming is solvable wait-free in shared-memory systems, whenever n is a power of a prime. Indeed, our model coincides with the shared-memory model whenever n = 3, and the minimum number of names for which renaming is possible in 3-process shared-memory systems is 5.

Cite as

Pierre Fraigniaud, Patrick Lambein-Monette, and Mikaël Rabie. Fault Tolerant Coloring of the Asynchronous Cycle. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2022.23,
  author =	{Fraigniaud, Pierre and Lambein-Monette, Patrick and Rabie, Mika\"{e}l},
  title =	{{Fault Tolerant Coloring of the Asynchronous Cycle}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.23},
  URN =		{urn:nbn:de:0030-drops-172147},
  doi =		{10.4230/LIPIcs.DISC.2022.23},
  annote =	{Keywords: graph coloring, LOCAL model, shared-memory model, immediate snapshot, renaming, wait-free algorithms}
}

Document

DOI: 10.4230/LIPIcs.SAND.2022.10

Computing Outside the Box: Average Consensus over Dynamic Networks

Authors: Bernadette Charron-Bost and Patrick Lambein-Monette

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract

Networked systems of autonomous agents, and applications thereof, often rely on the control primitive of average consensus, where the agents are to compute the average of private initial values. To provide reliable services that are easy to deploy, average consensus should continue to operate when the network is subject to frequent and unpredictable change, and should mobilize few computational resources, so that deterministic, low powered, and anonymous agents can partake in the network. In this stringent adversarial context, we investigate the implementation of average consensus by distributed algorithms over networks with bidirectional, but potentially short-lived, communication links. Inspired by convex recurrence rules for multi-agent systems, and the Metropolis average consensus rule in particular, we design a deterministic distributed algorithm that achieves asymptotic average consensus, which we show to operate in polynomial time in a synchronous temporal model. The algorithm is easy to implement, has low space and computational complexity, and is fully distributed, requiring neither symmetry-breaking devices like unique identifiers, nor global control or knowledge of the network. In the fully decentralized model that we adopt, to our knowledge, no other distributed average consensus algorithm has a better temporal complexity. Our approach distinguishes itself from classical convex recurrence rules in that the agent’s values may sometimes leave their previous convex hull. As a consequence, our convergence bound requires a subtle analysis, despite the syntactic simplicity of our algorithm.

Cite as

Bernadette Charron-Bost and Patrick Lambein-Monette. Computing Outside the Box: Average Consensus over Dynamic Networks. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:LIPIcs.SAND.2022.10,
  author =	{Charron-Bost, Bernadette and Lambein-Monette, Patrick},
  title =	{{Computing Outside the Box: Average Consensus over Dynamic Networks}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.10},
  URN =		{urn:nbn:de:0030-drops-159521},
  doi =		{10.4230/LIPIcs.SAND.2022.10},
  annote =	{Keywords: average consensus, dynamic networks, distributed algorithms, iterated averaging, Metropolis}
}

Search Results

Documents authored by Lambein-Monette, Patrick

Fault Tolerant Coloring of the Asynchronous Cycle

Abstract

Cite as

Computing Outside the Box: Average Consensus over Dynamic Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message